package 查找;

public class 二分法查找 {

    public static int BinarySearch(int key, int[] array) {
        // 数组开始标记
        int start = 0;
        // 数组结束标记
        int end = array.length - 1;
        while (start <= end) {
            // 数组中间值标记，这种写法比 (end + start)/2 要好，因为他不会存在整型溢出问题
            int mid = (end - start) / 2 + start;
            if (key < array[mid]) {
                end = mid - 1;
            } else if (key > array[mid]) {
                start = mid + 1;
            } else {
                // 返回满足要求的索引
                return mid;
            }
        }
        // 查找失败返回-1
        return -1;
    }

    public static void main(String[] args) {
        // 必须是有序数组
        int[] a = {2, 15, 20, 25, 29, 30, 31, 32, 40, 45, 46, 49, 50, 53, 55, 56,
          58, 60, 65, 70, 75, 78, 81, 92, 98, 99, 100, 120, 121, 130};
        int key = 70;
        int result = BinarySearch(key, a);
        System.out.println(key + "在有序数组里面的的索引为：" + result);

    }
}
